package com.zx.练习题._2020面试题;

import com.zx._12_算法.ListNode;
import java.util.ArrayList;
import java.util.List;
import org.junit.Assert;

/**
 * 【快手】判断一个链表是否为回文结构(进阶)
 * 给定一个链表，请判断该链表是否为回文结构。
 * 输入描述
 * n 表示链表的长度。
 * ai 表示链表节点的值
 * 输出描述
 * 如果为回文结构输出 "true" , 否则输出 "false"。
 */
public class 判断一个链表是否为回文结构 {

    public static void main(String[] args) {
        Assert.assertEquals(is1(ListNode.getNodes(1, 3, 3, 1)), true);
        Assert.assertEquals(is1(ListNode.getNodes(1, 3, 3, 2)), false);
        Assert.assertEquals(is1(ListNode.getNodes(1, 3, 3, 3, 1)), true);

        Assert.assertEquals(is2(ListNode.getNodes(1, 3, 3, 1)), true);
        Assert.assertEquals(is2(ListNode.getNodes(1, 3, 3, 2)), false);
        Assert.assertEquals(is2(ListNode.getNodes(1, 3, 3, 3, 1)), true);
    }

    // 存入集合，使用双指针判断
    private static boolean is1(ListNode head) {
        ListNode curr = head;
        List<ListNode> tmpList = new ArrayList<>();
        while (curr != null) {
            tmpList.add(curr);
            curr = curr.next;
        }

        int lo = 0, hi = tmpList.size() - 1;
        while (lo <= hi) {
            if (tmpList.get(lo).val != tmpList.get(hi).val) {
                return false;
            }
            lo++;
            hi--;
        }

        return true;
    }

    // 翻转半个链表
    private static boolean is2(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;//走一步
            fast = fast.next.next;//走两步
        }
        //翻转后半个链表，slow
        ListNode reverse = reverse(slow.next);

        while (reverse != null) {
            if (reverse.val != head.val) {
                return false;
            }
            reverse = reverse.next;
            head = head.next;
        }
        return true;
    }

    private static ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;

        while (cur != null) {
            ListNode next = cur.next;

            cur.next = prev;

            prev = cur;

            cur = next;
        }

        return prev;
    }
}
